package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * @ClassName: _1162_as_far_from_land_as_possible
 * @Description: 1162. 地图分析
 * 你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。如果网格上只有陆地或者海洋，请返回 -1。
 *
 * 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
 * 输出：2
 * 解释：
 * 海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
 * 示例 2：
 *
 *
 *
 * 输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
 * 输出：4
 * 解释：
 * 海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
 *
 *
 * 提示：
 *
 * n == grid.length
 * n == grid[i].length
 * 1 <= n <= 100
 * grid[i][j] 不是 0 就是 1
 *
 * https://leetcode-cn.com/problems/as-far-from-land-as-possible/
 *
 *
 * @Author: shouzimu
 * @Date: 2022/1/29 17:54
 */
public class _1162_as_far_from_land_as_possible {
    int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    /**
     * 代码cv的三叶姐的
     * @param grid
     * @return
     */
    public int maxDistance(int[][] grid) {
        int max = -1;
        int len = grid.length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (grid[i][j] == 0) {
                    max = Math.max(bfs(i, j, grid), max);
                }
            }
        }
        return max;
    }

    private int bfs(int x, int y, int[][] grid) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, y});
        int len = grid.length;
        Map<Integer, Integer> stepMap = new HashMap<>();
        stepMap.put(x * len + y, 0);
        while (!queue.isEmpty()) {
            int[] xy = queue.poll();
            int dx = xy[0];
            int dy = xy[1];
            int step = stepMap.get(dx * len + dy);
            if (grid[dx][dy] == 1) {
                return step;
            }

            for (int[] dir : dirs) {
                int nx = dx + dir[0], ny = dy + dir[1];
                if (nx < 0 || nx >= len || ny < 0 || ny >= len) {
                    continue;
                }
                int key = nx * len + ny;
                if (stepMap.containsKey(key)) {
                    continue;
                }
                queue.add(new int[]{nx, ny});
                stepMap.put(key, step + 1);
            }
        }
        return -1;
    }

    @Test
    public void maxDistanceTest() {
        Assert.assertEquals(4, maxDistance(new int[][]{{1, 0, 0}, {0, 0, 0}, {0, 0, 0}}));
        Assert.assertEquals(2, maxDistance(new int[][]{{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}));
    }


    public int maxDistanceDuoBFS(int[][] grid) {
        int len = grid.length;
        Map<Integer, Integer> stepMap = new HashMap<>();

        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                    stepMap.put(i * len + j, 0);
                }
            }
        }

        int res = 0;
        while (!queue.isEmpty()) {
            int[] xy = queue.poll();
            int dx = xy[0];
            int dy = xy[1];
            int step = stepMap.get(dx * len + dy);
            for (int[] dir : dirs) {
                int nx = dx + dir[0], ny = dy + dir[1];
                if (nx < 0 || nx >= len || ny < 0 || ny >= len) {
                    continue;
                }
                int key = nx * len + ny;
                if (stepMap.containsKey(key)) {
                    continue;
                }
                grid[nx][ny] = step + 1;
                queue.add(new int[]{nx, ny});
                res = Math.max(res, step + 1);
                stepMap.put(key, step + 1);
            }
        }

        return res;
    }
}
